{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Moving Stones Until Consecutive II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numMovesStonesII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移动石子直到连续 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个长度 <strong>无限 </strong>的数轴上，第 <code>i</code> 颗石子的位置为 <code>stones[i]</code>。如果一颗石子的位置最小/最大，那么该石子被称作 <strong>端点石子 </strong>。</p>\n",
    "\n",
    "<p>每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。</p>\n",
    "\n",
    "<p>值得注意的是，如果石子像 <code>stones = [1,2,5]</code> 这样，你将 <strong>无法 </strong>移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。</p>\n",
    "\n",
    "<p>当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。</p>\n",
    "\n",
    "<p>要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：<code>answer = [minimum_moves, maximum_moves]</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[7,4,9]\n",
    "<strong>输出：</strong>[1,2]\n",
    "<strong>解释：</strong>\n",
    "我们可以移动一次，4 -> 8，游戏结束。\n",
    "或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[6,5,4,3,10]\n",
    "<strong>输出：</strong>[2,3]\n",
    "<strong>解释：</strong>\n",
    "我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。\n",
    "或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。\n",
    "注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[100,101,104,102,103]\n",
    "<strong>输出：</strong>[0,0]</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 <= stones.length <= 10^4</code></li>\n",
    "\t<li><code>1 <= stones[i] <= 10^9</code></li>\n",
    "\t<li><code>stones[i]</code> 的值各不相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [moving-stones-until-consecutive-ii](https://leetcode.cn/problems/moving-stones-until-consecutive-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [moving-stones-until-consecutive-ii](https://leetcode.cn/problems/moving-stones-until-consecutive-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,4,9]', '[6,5,4,3,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        stones.sort()\n",
    "        n = len(stones)\n",
    "        e1 = stones[-2] - stones[0] - n + 2\n",
    "        e2 = stones[-1] - stones[1] - n + 2\n",
    "        max_move = max(e1, e2)\n",
    "        if e1 == 0 or e2 == 0:\n",
    "            return [min(2, max_move), max_move]\n",
    "        max_cnt = left = 0\n",
    "        for right, sr in enumerate(stones):\n",
    "            while sr - stones[left] + 1 > n:\n",
    "                left += 1\n",
    "            max_cnt = max(max_cnt, right - left + 1)\n",
    "        return [n - max_cnt, max_move]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        stones.sort()\n",
    "        n = len(stones)\n",
    "        a = stones[-2] - stones[0] - n + 2\n",
    "        b = stones[-1] - stones[1] - n + 2\n",
    "        ma = max(a, b)\n",
    "        if a == 0 or b == 0:\n",
    "            return [min(2, ma), ma]\n",
    "        \n",
    "        maxcnt = l = 0\n",
    "        for r, stone in enumerate(stones):\n",
    "            while stone - stones[l] + 1 > n:\n",
    "                l += 1\n",
    "            maxcnt = max(maxcnt, r - l + 1)\n",
    "        \n",
    "        return [n - maxcnt, ma]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 下跳棋\n",
    "    # https://leetcode.cn/problems/moving-stones-until-consecutive-ii/solutions/2212638/tu-jie-xia-tiao-qi-pythonjavacgo-by-endl-r1eb/\n",
    "    def numMovesStonesII(self, s: List[int]) -> List[int]:\n",
    "        s.sort()\n",
    "        n = len(s)\n",
    "        e1 = s[-2] - s[0] - n + 2\n",
    "        e2 = s[-1] - s[1] - n + 2  # 计算空位\n",
    "        max_move = max(e1, e2)\n",
    "        if e1 == 0 or e2 == 0:  # 特殊情况：没有空位\n",
    "            return [min(2, max_move), max_move]\n",
    "\n",
    "        max_cnt = left = 0\n",
    "        for right, sr in enumerate(s):  # 滑动窗口：枚举右端点所在石子\n",
    "            while sr - s[left] + 1 > n:  # 窗口长度大于 n\n",
    "                left += 1  # 缩小窗口长度\n",
    "\n",
    "            max_cnt = max(max_cnt, right - left + 1)  # 维护窗口内的最大石子数\n",
    "\n",
    "        return [n - max_cnt, max_move]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        stones.sort()\n",
    "        N = len(stones)\n",
    "        mn, r = N, 0\n",
    "        for l in range(N):\n",
    "            while r < N - 1 and stones[r + 1] - stones[l] + 1 <= N:\n",
    "                r += 1\n",
    "            \n",
    "            if r - l + 1 == N - 1 and stones[r] - stones[l] + 1 == N - 1:\n",
    "                mn = min(mn, 2)\n",
    "            else:\n",
    "                mn = min(mn, N - (r - l + 1))\n",
    "\n",
    "        return [mn, max(stones[-1] - stones[1], stones[-2] - stones[0]) - N + 2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        #copy\n",
    "        stones.sort()\n",
    "        n = len(stones)\n",
    "        e1 = stones[-2] -stones[0] -n+2\n",
    "        e2 = stones[-1]-stones[1]-n+2\n",
    "        maxmove = max(e1,e2)\n",
    "        if e1 ==0 or e2 ==0:\n",
    "            return [min(2,maxmove),maxmove]\n",
    "        maxcnt = left = 0\n",
    "        for right ,sr in enumerate(stones):\n",
    "            while sr - stones[left]+1>n:\n",
    "                left += 1\n",
    "            maxcnt = max(maxcnt,right-left+1)\n",
    "        return [n-maxcnt,maxmove]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        stones.sort()\n",
    "        n = len(stones)\n",
    "        if stones[-1] - stones[0] + 1 == n:\n",
    "            return [0, 0]\n",
    "        vmax = max(stones[-2]-stones[0]+1, stones[-1]-stones[1]+1) - (n-1)\n",
    "        left, right = 0, 0\n",
    "        vmin = n\n",
    "        while left < n:\n",
    "            while right < n and stones[right] - stones[left] + 1 <= n:\n",
    "                right += 1\n",
    "            if right - left == n - 1 and stones[right-1] - stones[left] + 1 == n - 1:\n",
    "                vmin = min(vmin, 2)\n",
    "            else:\n",
    "                vmin = min(vmin, n - (right-left))\n",
    "            left += 1\n",
    "        return [vmin, vmax]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, s: List[int]) -> List[int]:\n",
    "        s.sort()\n",
    "        n = len(s)\n",
    "        tot = s[-1] - s[0] + 1 - n\n",
    "        mx = tot - min(s[1] - s[0] - 1, s[-1] - s[-2] - 1)\n",
    "\n",
    "        mn = mx\n",
    "        l = 0\n",
    "        for r in range(n):\n",
    "            while s[r] - s[l] + 1 > n:\n",
    "                l += 1\n",
    "            t = n - (r - l + 1)\n",
    "            if r - l + 1 == n - 1 and s[r] - s[l] + 1 == n - 1:\n",
    "                t = 2\n",
    "            mn = min(mn, t)\n",
    "\n",
    "        return [mn, mx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        n = len(stones)\n",
    "        stones.sort()\n",
    "        if stones[-1] - stones[0] + 1 ==n:\n",
    "            return [0,0]\n",
    "        \n",
    "        ma = max(stones[-2]- stones[0] + 1, stones[-1] - stones[1] + 1) - (n-1)\n",
    "        mi = n\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j + 1 < n and stones[j+1] - stones[i] + 1 <= n:\n",
    "                j += 1\n",
    "            if j + 1 - i == n-1 and stones[j] - stones[i] + 1 == n-1:\n",
    "                mi = min(mi,2)\n",
    "            else:\n",
    "                mi = min(mi,n-(j-i+1))\n",
    "        return [mi,ma] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "      stones.sort()\n",
    "      n = len(stones)\n",
    "      \n",
    "      # Calculate max_moves\n",
    "      max_moves = max(stones[-1] - stones[1] - n + 2, stones[-2] - stones[0] - n + 2)\n",
    "      \n",
    "      # Calculate min_moves using sliding window\n",
    "      min_moves = n\n",
    "      j = 0\n",
    "      for i in range(n):\n",
    "          while j < n and stones[j] - stones[i] < n:\n",
    "              j += 1\n",
    "          if j - i == n - 1 and stones[j-1] - stones[i] == n - 2:\n",
    "              min_moves = min(min_moves, 2)\n",
    "          else:\n",
    "              min_moves = min(min_moves, n - (j - i))\n",
    "      \n",
    "      return [min_moves, max_moves]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        s = stones\n",
    "        s.sort()\n",
    "        n = len(s)\n",
    "        e1 = s[-2] - s[0] - n + 2\n",
    "        e2 = s[-1] - s[1] - n + 2\n",
    "        max_move = max(e1, e2)\n",
    "        if e1==0 or e2 == 0:\n",
    "            return [min(2, max_move), max_move]\n",
    "        max_cnt = left = 0\n",
    "        for right, sr in enumerate(s):\n",
    "            while sr - s[left] + 1 > n:\n",
    "                left += 1\n",
    "            max_cnt = max(max_cnt, right - left + 1)\n",
    "        \n",
    "        return [n-max_cnt, max_move]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        stones.sort()\n",
    "        mi = n = len(stones)\n",
    "        mx = max(stones[-1] - stones[1] + 1, stones[-2] - stones[0] + 1) - (n - 1)\n",
    "        i = 0\n",
    "        for j, x in enumerate(stones):\n",
    "            while x - stones[i] + 1 > n:\n",
    "                i += 1\n",
    "            if j - i + 1 == n - 1 and x - stones[i] + 1 == n - 1:\n",
    "                mi = min(mi, 2)\n",
    "            else:\n",
    "                mi = min(mi, n - (j - i + 1))\n",
    "        return [mi, mx]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, s: List[int]) -> List[int]:\n",
    "        s.sort()\n",
    "        n = len(s)\n",
    "        tot = s[-1] - s[0] + 1 - n\n",
    "        mx = tot - min(s[1] - s[0] - 1, s[-1] - s[-2] - 1)\n",
    "\n",
    "        mn = mx\n",
    "        l = 0\n",
    "        for r in range(n):\n",
    "            while s[r] - s[l] + 1 > n:\n",
    "                l += 1\n",
    "            t = n - (r - l + 1)\n",
    "            if r - l + 1 == s[r] - s[l] + 1 == n - 1:\n",
    "                t = 2\n",
    "            mn = min(mn, t)\n",
    "\n",
    "        return [mn, mx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        s = sorted(stones)\n",
    "        n = len(s)\n",
    "        e1 = s[n-2]-s[0]-1-(n-3)\n",
    "        e2 = s[n-1]-s[1]-1-(n-3)\n",
    "        maxmove = max(e1,e2)\n",
    "        if e1==0 or e2==0:\n",
    "            return [min(2,maxmove),maxmove]\n",
    "        \n",
    "        maxcnt, left = 0, 0\n",
    "        for right, st in enumerate(s):\n",
    "            while st-s[left]+1>n:\n",
    "                left += 1\n",
    "            maxcnt = max(maxcnt,right-left+1)\n",
    "        return [n-maxcnt, maxmove]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        n = len(stones)\n",
    "        stones.sort()\n",
    "        if stones[-1] - stones[0] + 1 == n:\n",
    "            return [0, 0]\n",
    "        ma = max(stones[-2] - stones[0] + 1, stones[-1] - stones[1] + 1) - (n - 1)\n",
    "        mi = n\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j + 1 < n and stones[j + 1] - stones[i] + 1 <= n:\n",
    "                j += 1\n",
    "            if j - i + 1 == n - 1 and stones[j] - stones[i] + 1 == n - 1:\n",
    "                mi = min(mi, 2)\n",
    "            else:\n",
    "                mi = min(mi, n - (j - i + 1))\n",
    "        return [mi, ma]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        stones.sort()\n",
    "        n=len(stones)\n",
    "        if stones[-1] - stones[0] + 1 == n:\n",
    "            return [0, 0]\n",
    "        ma = max(stones[-2] - stones[0] + 1, stones[-1] - stones[1] + 1) - (n - 1)\n",
    "        mi= n\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j + 1 < n and stones[j + 1] - stones[i] + 1 <= n:\n",
    "                j += 1\n",
    "            if j - i + 1 == n - 1 and stones[j] - stones[i] + 1 == n - 1:\n",
    "                mi = min(mi, 2)\n",
    "            else:\n",
    "                mi = min(mi, n - (j - i + 1))\n",
    "        return [mi, ma]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        n = len(stones)\n",
    "        stones.sort()\n",
    "\n",
    "        if stones[n - 1] - stones[0] + 1 == n:\n",
    "            return [0, 0]\n",
    "\n",
    "        ma = max(stones[-2] - stones[0], stones[-1] - stones[1]) + 1 - (n - 1)\n",
    "\n",
    "        mi = n\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j + 1 < n and stones[j + 1] - stones[i] + 1 <= n:\n",
    "                j += 1\n",
    "\n",
    "            if j - i + 1 == n - 1 and stones[j] - stones[i] + 1 == n - 1:\n",
    "                mi = min(mi, 2)\n",
    "\n",
    "            else:\n",
    "                mi = min(mi, n - (j - i + 1))\n",
    "\n",
    "        return [mi, ma]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        n = len(stones)\n",
    "        stones.sort()\n",
    "        if stones[-1] - stones[0] +1 == n:\n",
    "            return [0, 0]\n",
    "        ma = max(stones[-2] - stones[0] + 1, stones[-1] - stones[1] + 1) - (n - 1)\n",
    "        mi = n\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j + 1 < n and stones[j + 1] - stones[i] + 1 <= n:\n",
    "                j += 1\n",
    "            if j - i + 1 == n - 1 and stones[j] - stones[i] + 1 == n - 1:\n",
    "                mi = min(mi, 2)\n",
    "            else:\n",
    "                mi = min(mi, n - (j -i + 1))\n",
    "        return [mi, ma]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, s: List[int]) -> List[int]:\n",
    "        s.sort()\n",
    "        n = len(s)\n",
    "        e1 = s[-2] - s[0] - n + 2\n",
    "        e2 = s[-1] - s[1] - n + 2  # 计算空位\n",
    "        max_move = max(e1, e2)\n",
    "        if e1 == 0 or e2 == 0:  # 特殊情况：没有空位\n",
    "            return [min(2, max_move), max_move]\n",
    "        max_cnt = left = 0\n",
    "        for right, sr in enumerate(s):  # 滑动窗口：枚举右端点所在石子\n",
    "            while sr - s[left] + 1 > n:  # 窗口长度大于 n\n",
    "                left += 1  # 缩小窗口长度\n",
    "            max_cnt = max(max_cnt, right - left + 1)  # 维护窗口内的最大石子数\n",
    "        return [n - max_cnt, max_move]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        n = len(stones)\n",
    "        stones.sort()\n",
    "        if stones[-1] - stones[0] + 1 == n:\n",
    "            return [0, 0]\n",
    "        ma = max(stones[-2] - stones[0] + 1, stones[-1] - stones[1] + 1) - (n - 1)\n",
    "        mi = n\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j + 1 < n and stones[j + 1] - stones[i] + 1 <= n:\n",
    "                j += 1\n",
    "            if j - i + 1 == n - 1 and stones[j] - stones[i] + 1 == n - 1:\n",
    "                mi = min(mi, 2)\n",
    "            else:\n",
    "                mi = min(mi, n - (j - i + 1))\n",
    "        return [mi, ma]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        stones.sort()\n",
    "        n = len(stones)\n",
    "        max_gap = max(stones[-1] - stones[1] - (n-2), stones[-2] - stones[0] - (n-2))\n",
    "        min_gap = float('inf')\n",
    "        j = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while j < n and stones[j] - stones[i] + 1 <= n:\n",
    "                j += 1\n",
    "            cost = n - (j - i)\n",
    "            if j - i == n - 1 and stones[j - 1] - stones[i] + 1 == n - 1:\n",
    "                cost = 2\n",
    "            min_gap = min(min_gap, cost)\n",
    "        return [min_gap, max_gap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        stones.sort()\n",
    "        n, mn, end = len(stones), 1, 0\n",
    "        mx = max(stones[-2] - stones[0], stones[-1] - stones[1]) + 2 - n\n",
    "        for i,v in enumerate(stones):\n",
    "            while end < n and stones[end]-v < n: end += 1\n",
    "            mn = max(mn, end - i)\n",
    "        if mn==n-1 and ((stones[n-2]-stones[0] == n-2 and stones[n-1] - stones[n-2] > 2) or (stones[n-1]-stones[1] == n-2 and stones[1] - stones[0] > 2)): mn -= 1\n",
    "        return [n - mn,mx]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "      n=len(stones)\n",
    "      stones.sort()\n",
    "      # 计算最大play次数\n",
    "      # 每次都让同一侧的石子去跳，这样的话，除了第一次起跳，剩下的都只可能让区间的大小-1，最终形成一个连续区间。假设每次都让最左侧的石头跳，那么结果为stones[-1]-stones[1]-1-(n-3)=stones[-1]-stones[1]-n+2,因此结果为max(stones[-1]-stones[1]-n+2,stones[-2]-stones[0]-n+2)\n",
    "      # 计算最小play次数\n",
    "      # 维护一个大小为n的窗口。首先讨论特殊情况，如果stones[1]到stones[-1]或stones[0]到stones[-2]已经连续，那么需要最小要跳动的次数为2。不然的话，最小跳动次数为min(n-max窗口中石子个数)\n",
    "      max1=stones[-1]-stones[1]-n+2\n",
    "      max2=stones[-2]-stones[0]-n+2\n",
    "      max_ret=max(max1,max2)\n",
    "      if max1==0 or max2==0:\n",
    "        return [min(2,max_ret),max_ret]\n",
    "      max_window=0\n",
    "      l=0\n",
    "      for r,r_bound in enumerate(stones):\n",
    "        # 窗口长度大于n\n",
    "        while r_bound-stones[l]+1>n:\n",
    "          l+=1\n",
    "        # 使得窗口长度小于等于n\n",
    "        max_window=max(max_window,r-l+1)\n",
    "      return [n-max_window,max_ret]\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMovesStonesII(self, stones: List[int]) -> List[int]:\n",
    "        # 最小的移动次数等于 数组长度 减去最长连续子串的长度，子串可以有一个空位\n",
    "        # 最大的移动次数，向一个位置进行靠拢\n",
    "    # 上面这玩意写的乱七八糟\n",
    "        n = len(stones)\n",
    "        stones.sort()\n",
    "        if stones[-1] - stones[0] + 1 == n:\n",
    "            return [0,0]\n",
    "        ma = max(stones[-2] - stones[0] + 1,stones[-1] - stones[1] + 1) -(n - 1)\n",
    "        mi =  n\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j + 1 < n and stones[j + 1] - stones[i] + 1 <= n:\n",
    "                j += 1\n",
    "            if j -i + 1 == n - 1 and stones[j] - stones[i] + 1 == n -1:\n",
    "                mi = min(mi,2)\n",
    "            else:\n",
    "                mi = min(mi,n-(j-i+1))\n",
    "        return [mi,ma]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
